//思路就是我们没有不要完全进行排序 只要我们前面几项的大于等于我们的要的几个数即可 此时直接返回
//只要保证要求的前几个是有序的即可
class Solution {
public:
    vector<int>ret;
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        if(cnt==0) return {};
        srand(time(nullptr));
        quicksort(stock,0,stock.size()-1,cnt);
        return {stock.begin(),stock.begin()+cnt};
    }

    void quicksort(vector<int>&stock,int left,int right,int cnt)
    {

        int key=stock[rand()%(right-left+1)+left];
        int i=left;
        int begin=left-1;
        int end=right+1;
        for(i=left;i<end;)
        {
            if(stock[i]==key) i++;
            else if(stock[i]<key) swap(stock[i++],stock[++begin]);
            else swap(stock[--end],stock[i]);
        }
        int a=begin-left+1;
        int b=end-begin-1;
        if(a>=cnt) return quicksort(stock,left,begin,cnt);
        else if(a+b>=cnt) return;
        else return quicksort(stock,end,right,cnt-a-b);
    }
};